#include <iostream>
#include <string>
using namespace std;

const int N = 100010;
int m, K, x;
string op;

class heap
{
private:
    int h[N];
    int ph[N];
    int hp[N];
    int size;
    int k;

public:
    heap();
    void h_swap(int a, int b);
    void down(int u);
    void up(int u);
    void alter(int k, int x);
    void add(int x);
    void del(int k);
    int pop();
    int MIN();
};

heap::heap()
{
    size = 0;
    k = 0;
}

void heap::h_swap(int a, int b)
{
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
    return;
}

void heap::up(int u)
{
    while (u / 2 && h[u / 2] > h[u])
    {
        h_swap(u / 2, u);
        u >>= 1;
    }
    return;
}

void heap::down(int u)
{
    int t = u;
    if (2 * u <= size && h[2 * u] < h[t])
        t = 2 * u;
    if (2 * u + 1 <= size && h[2 * u + 1] < h[t])
        t = 2 * u + 1;
    if (t != u)
    {
        h_swap(t, u);
        down(t);
    }
    return;
}

int heap::MIN()
{
    return h[1];
}

int heap::pop()
{
    int min = h[1];
    del(hp[1]);
    return min;
}

void heap::add(int x)
{
    size++;
    k++;
    h[size] = x;
    hp[size] = k;
    ph[k] = size;
    up(size);
    return;
}

void heap::del(int k)
{
    k = ph[k];
    h_swap(k, size);
    size--;
    up(k);
    down(k);
    return;
}

void heap::alter(int k, int x)
{
    k = ph[k];
    h[k] = x;
    up(k);
    down(k);
    return;
}

int main()
{
    cin >> m;
    heap H;
    while (m--)
    {
        cin >> op;
        if (op[0] == 'I')
        {
            cin >> x;
            H.add(x);
        }
        else if (op[0] == 'P')
            cout << H.MIN() << endl;
        else if (op[1] == 'M')
            H.pop();
        else if (op[0] == 'C')
        {
            cin >> K >> x;
            H.alter(K, x);
        }
        else
        {
            cin >> K;
            H.del(K);
        }
    }
    return 0;
}